package datastructure.hash.solution;

import org.junit.jupiter.api.Test;

import java.util.*;

public class SolutionHashKey {
    @Test
    public void test() {
        String[] strs = {"cab","tin","pew","duh","may","ill","buy","bar","max","doc"};
        List<List<String>> lists = groupAnagrams2(strs);
        System.out.println(lists);
    }
    /**
     * 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
     * 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
     * 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
     * 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
     * 输入: strs = [""]
     * 输出: [[""]]
     * 输入: strs = ["a"]
     * 输出: [["a"]]
     * @param strs
     * @return
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            List<String> strings = map.computeIfAbsent(new String(chars), k -> new ArrayList<>());
            strings.add(str);
        }
        return new ArrayList<>(map.values());
    }
    public List<List<String>> groupAnagrams2(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String str : strs) {
            char[] chars = str.toCharArray();
            int[] hash = new int[26];
            for (char c : chars) {
                hash[c - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < hash.length; i++) {
                if (hash[i] > 0) {
                    sb.append((char)(i+'a')).append(hash[i]);
                }
            }
            List<String> strings = map.computeIfAbsent(sb.toString(), k -> new ArrayList<>());
            strings.add(str);
        }
        return new ArrayList<>(map.values());
    }

    /**
     * 请你判断一个9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
     * 数字1-9在每一行只能出现一次。
     * 数字1-9在每一列只能出现一次。
     * 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
     * 注意：
     * 一个有效的数独（部分已被填充）不一定是可解的。
     * 只需要根据以上规则，验证已经填入的数字是否有效即可。
     * 空白格用'.'表示。
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {

        for (char[] chars : board) {
            HashSet<Character> setRow = new HashSet<>();
            for (char aChar : chars) {
                if (aChar!= '.' && !setRow.add(aChar)) {
                    return false;
                }
            }
        }
        for (int i = 0; i < board.length; i++) {
            HashSet<Character> setLine = new HashSet<>();
            for (char[] chars : board) {
                if (chars[i]!= '.' && !setLine.add(chars[i])) {
                    return false;
                }
            }
        }
        for (int i = 0; i < board.length; i+=3) {
            for (int j = 0; j < board.length; j+=3) {
                HashSet<Character> setLine = new HashSet<>();
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 3; l++) {
                        if (board[i+k][j+l]!= '.' &&!setLine.add(board[i+k][j+l])) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 给你一棵二叉树的根节点 root ，返回所有 重复的子树 。
     * 对于同一类的重复子树，你只需要返回其中任意 一棵 的根结点即可。
     * 如果两棵树具有 相同的结构 和 相同的结点值 ，则认为二者是 重复 的。
     * 输入：root = [1,2,3,4,null,2,4,null,null,4]
     * 输出：[[2,4],[4]]
     * 输入：root = [2,1,1]
     * 输出：[[1]]
     * 输入：root = [2,2,2,3,null,3,null]
     * 输出：[[2,3],[3]]
     * 每个TreeNode各不相同，即使他们的值相同，但是是不同的对象
     */
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        HashMap<String, TreeNode> set = new HashMap<>();
        HashSet<TreeNode> result = new HashSet<>();
        findDuplicateSubtrees0(set,result,root);
        return new ArrayList<>(result);
    }
    private String findDuplicateSubtrees0(HashMap<String, TreeNode> set, HashSet<TreeNode> result, TreeNode node){
        if (node == null) {
            return "";
        }
        String string = "n"+node.val +"l"+
                findDuplicateSubtrees0(set, result, node.left) +"r"+
                findDuplicateSubtrees0(set, result, node.right);
        if (set.containsKey(string)) {
            TreeNode treeNode = set.get(string);
            result.add(treeNode);
        } else  {
            set.put(string, node);
        }
        return string;
    }

    /**
     * 给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
     * 0 <= i, j, k, l < n
     * nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
     * 示例 1：
     * 输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
     * 输出：2
     * 解释：
     * 两个元组如下：
     * 1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
     * 2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
     * 示例 2：
     * 输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
     * 输出：1
     */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int count = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                for (int k = 0; k < nums3.length; k++) {
                    for (int l = 0; l < nums4.length; l++) {
                        if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
    public int fourSumCount2(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i : nums1) {
            for (int i1 : nums2) {
                map.put(i + i1, map.getOrDefault(i+i1,0)+1);
            }
        }
        int result = 0;
        for (int i : nums3) {
            for (int i1 : nums4) {
                Integer num = -i-i1;
                if (map.containsKey(num)) {
                    result += map.get(num);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] board = {
                { 0, 1, 2, 3, 4, 5, 6, 7, 8},
                {10,11,12,13,14,15,16,17,18},
                {20,21,22,23,24,25,26,27,28},
                {30,31,32,33,34,35,36,37,38},
                {40,41,42,43,44,45,46,47,48},
                {50,51,52,53,54,55,56,57,58},
                {60,61,62,63,64,65,66,67,68},
                {70,71,72,73,74,75,76,77,78},
                {80,81,82,83,84,85,86,87,88},
        };
        for (int i = 0; i < board.length; i+=3) {
            for (int j = 0; j < board.length; j+=3) {
                for (int k = 0; k < 3; k++) {
                    for (int l = 0; l < 3; l++) {
                        System.out.print(board[i+k][j+l]);
                        System.out.print(",");
                    }
                }
                System.out.println();
            }
        }
    }
}
